/*
 * All Rights Reserved.
 *
 * Author : Madhur Raj
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "structs.h"
#include "readfile.h"

/* Forward declarations */
extern void readfile();

Node *front, *tail;
ArrS arr[MAXVAL];
int   numVar;

Node* getListNode ()
{
   Node *newNode = (Node*)malloc(sizeof(Node));
   if (front == NULL)
   {
      front = tail = newNode;
      newNode->next = newNode->prev = NULL;
   }
   else
   {
      tail->next = newNode;
      newNode->prev = tail;
      tail = newNode;
   }

   return (newNode);
}

int* getNode()
{
   Node *newNode = getListNode();
   numVar++;
   arr[count++].arr = &(newNode->data);
   arr[count++].node = newNode;
   return (&(newNode->data));
}

void printNodes()
{
   Node *tmp = front;

   while(tmp)
   {
      printf("%d\n", tmp->data);
      tmp = tmp->next;
   }
}

void merge(int left, int right, int count)
{
   int left; middlei;

   middlei = count/2;
   lefti = left;

   while(lefti < middlei || middlei <= right)
   {
      if (*arr[lefti] < *arr[middlei])
      {
         lefti++;
      }
      else
      {
         SWAP(arr[lefti], arr[middlei]);
      }
   }
}

void mergeSort(int left, int right ,int count)
{
   int middle; 

   if (count == 1)
      return (count);

   middle = (count/2);

   left = mergeSort(left, middle, middle);
   right = mergeSort(middle, right, count-middle);

   merge(left, right, count);

   return;
}

void printResult()
{
   FILE *fp;
   Node *tmp;

   fp = fopen("output.txt", "w+");
   if (!fp)
   {
      printf("Unable to open file\n");
      exit(0);
   }

   tmp = front;
   while (tmp)
   {
      fprintf(fp, "%d ", tmp->data);
      tmp = tmp->next;
   }
   fclose(fp);
}

int main()
{
   struct timeval start, finish;
   int count = COUNT;
   front = tail = NULL;
   readfile();
   gettimeofday(&start, NULL);
   do
   {
      mergeSort();
      mergeSortRev();
   } while(--count);
   gettimeofday(&finish, NULL);
   printf("Time taken %ld sec %ld microsec\n", finish.tv_sec - start.tv_sec,
                                            finish.tv_usec - start.tv_usec);
    
   printResult();
#ifdef DEBUG
   printNodes();
#endif
   return(0);
}
